package Hot100;

import common.ListNode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author zhangmin
 * @create 2022-01-10 22:13
 */
public class calcEquation399 {

    /**
     * 399. 除法求值
     * 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。
     * 每个 Ai 或 Bi 是一个表示单个变量的字符串。
     * 另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
     * 返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
     * 思路：并查集，代替dfs的查找
     *  不同的变量的比值转换成为相同的变量的比值，这样在做除法的时候就可以消去相同的变量，然后再计算转换成相同变量以后的系数的比值
     *  构建有向图：可以构建equations的有权图
     *  路径压缩：可以把queries中的不同变量用用一个变量表示，就能在o1时间得到结果。效果是：在查询一个结点 a 的根结点同时，把结点 a 到根结点的沿途所有结点的父亲结点都指向根结点。
     *  需要压缩的节点的父节点改成根节点后，需要将权重从当前节点到根节点的经过的有向边的权重乘积
     * */
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        //1、构建并查集,预处理，将变量的值与 并查集中的节点id 进行映射，使得并查集的底层使用数组实现，方便编码
        int n=equations.size();
        UnionFind unionFind=new UnionFind(2*n);
        Map<String,Integer> map=new HashMap<>();
        int id=0;
        for (int i = 0; i < n; i++) {
            List<String> equation=equations.get(i);
            String cur1 = equation.get(0);
            String cur2 = equation.get(1);
            if (!map.containsKey(cur1)){
                map.put(cur1,id);
                id++;
            }
            if (!map.containsKey(cur2)){
                map.put(cur2,id);
                id++;
            }
            unionFind.union(map.get(cur1),map.get(cur2),values[i]);
        }
        //2、查询结果
        int n1=queries.size();
        double[] res=new double[n1];
        for (int i = 0; i < n1; i++) {
            String cur1 = queries.get(i).get(0);
            String cur2 = queries.get(i).get(1);
            Integer id1 = map.get(cur1);
            Integer id2 = map.get(cur2);
            if (id1==null||id2==null){
                res[i]=-1.0d;
            }else {
                res[i]=unionFind.connected(id1,id2);
            }
        }
        return res;
    }

    public class UnionFind {
        // 存储若干棵树，记录每个节点的父节点
        private int[] parent;
        // 记录指向父节点的权重
        private double[] weight;

        public UnionFind(int n) {
            parent=new int[n];
            weight=new double[n];
            for (int i = 0; i < n; i++) {
                //初始状态每个节点的父节点为自己
                parent[i] = i;
                weight[i]=1.0d;
            }
        }

        /* 将 p 和 q 连通 */
        public void union(int p, int q,double value) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ)
                return;

            parent[rootP]=rootQ;
            weight[rootP]=weight[q]*value/weight[p];
        }

        /* 判断 p 和 q 是否互相连通 */
        double connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            // 处于同一棵树上的节点，相互连通
            if (rootP == rootQ){
                return weight[p]/weight[q];
            }else {
                return -1.0d;
            }
        }

        /* 返回节点 x 的根节点 */
        private int find(int x) {
            if (x!=parent[x]){
                int cur=parent[x];
                parent[x]=find(parent[x]);
                weight[x]*=weight[cur];
            }
            return parent[x];
        }

    }



}
